//----------------------------------------------
// Purpose: Test the binary search function
// Author:  John Gauch
//----------------------------------------------

#include <cstdlib> 
#include <iostream>
using namespace std;

//----------------------------------------------
// Initialize an array to contain sorted numbers.
//----------------------------------------------
void init_array(int data[], int low, int high)
{
   data[low] = random() % 10;
   for (int index = low + 1; index <= high; index++)
      data[index] = data[index - 1] + 1 + random() % 10;
}

//----------------------------------------------
// Print contents of array.
//----------------------------------------------
void print_array(int data[], int low, int high)
{
   for (int index = low; index <= high; index++)
      cout << "data[" << index << "] = " << data[index] << endl;
}

//----------------------------------------------
// Perform binary search on sorted array.
//----------------------------------------------
int binary_search(int data[], int value, int low, int high)
{
   // Calculate midpoint index
   int mid = (low + high) / 2;
   // cout << low << " " << mid << " " << high << endl;

   // Check termination condition
   if (low > high)
      return -1;

   // Check if value is found
   else if (data[mid] == value)
      return mid;

   // Search to the left
   else if (data[mid] > value)
      return binary_search(data, value, low, mid - 1);

   // Search to the right
   else 
      return binary_search(data, value, mid + 1, high);
}

//----------------------------------------------
// Main program.
//----------------------------------------------
int main()
{
   // Initialize random sorted array
   const int SIZE = 100;
   int data[SIZE];
   init_array(data, 0, SIZE - 1);
   print_array(data, 0, SIZE - 1);

   // Search sorted array for values inside array
   for (int index = 0; index < SIZE; index++)
   {
      int pos = binary_search(data, data[index], 0, SIZE - 1);
      if (pos >= 0)
	 cout << "Found " << data[index] << " at " << pos << endl;

      else
	 cout << "Value " << data[index] << " not found" << endl;
   }

   // Search sorted array for values outside array
   int pos = binary_search(data, data[0] - 10, 0, SIZE - 1);
   if (pos >= 0)
      cout << "Found " << data[0] - 10 << " at " << pos << endl;
   else
      cout << "Value " << data[0] - 10 << " not found" << endl;

   // Search sorted array for values outside array
   pos = binary_search(data, data[SIZE - 1] + 10, 0, SIZE - 1);
   if (pos >= 0)
      cout << "Found " << data[SIZE - 1] + 10 << " at " << pos << endl;
   else
      cout << "Value " << data[SIZE - 1] + 10 << " not found" << endl;

   // Search sorted array for values between other values
   for (int index = 1; index < SIZE; index++)
   {
      int value = (data[index - 1] + data[index]) / 2;
      int pos = binary_search(data, value, 0, SIZE - 1);
      if (pos >= 0)
	 cout << "Found " << value << " at " << pos << endl;
      else
	 cout << "Value " << value << " not found" << endl;
   }
}